package binaryTree.review;

/**
 * 3.7
* */
public class MergeSort1 {
    public int[] mergeSort(int[] nums){
        if (nums.length==0){
            return null;
        }
        int[] temp = new int[nums.length];
        sort(nums,0, nums.length-1,temp);
        return  nums;
    }

    public  void sort(int[] nums,int lo,int hi,int[] temp){
       //todo:一定是等于的时候就不能再进行划分了　
        if (lo>=hi){
            return;
        }
        int mid=(lo+hi)/2;
        sort(nums,lo,mid,temp);
        sort(nums,mid+1,hi,temp);
        merge(nums,lo,mid,hi,temp);
    }

    public  void merge(int[] nums,int lo,int mid,int hi,int[] temp){
        int i=0;
        int j=lo;
        int k=mid+1;
        while (j<mid+1&&k<=hi){
            if (nums[j]<nums[k]){
                temp[i++]=nums[j++];
            }
            else{
                temp[i++]=nums[k++];
            }
        }
        while (j<mid+1){
            temp[i++]=nums[j++];
        }
        while (k<=hi){
            temp[i++]=nums[k++];
        }
//        todo:错误写法　　l < temp.length　　temp的length是固定的　　所以这样写错误
//        for (int l =0; l < temp.length; l++) {
            for (int l =0; l < i; l++) {

                nums[lo+l]=temp[l];
        }

    }

    public static void main(String[] args) {
        MergeSort1 mergeSort = new MergeSort1();
        int[] nums={5,2,1,6,4};
        mergeSort.mergeSort(nums);

        for (int a: nums
        ) {
            System.out.println(a);
        }
    }


}
